---

deStack.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deStack.hpp
///
/// @brief Templated Stack/Queue class
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Sept 2001
/// @author Assassin
/// @remarks Creation
///
/// @date Jan 2002
/// @author Assassin
/// @remarks Bug fixes
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DESTACK_HPP
#define DESTACK_HPP


#include "deGlobalTypes.hpp"


// Structures defined in this header

typedef struct StackNode StackNode;



// Enums

#pragma warning (disable : 4710)

/// templated stack (or queue) storage class
template <class T>
class deTStack
{
public:
    enum deStackType
    {
        LIFO_STACK = 0,
        FIFO_STACK = 1,
        StackType_32bit = 0x7fffffff
    };
    deTStack();
    deTStack(deStackType PopOrder);
    deTStack(const deTStack &Stack);
    ~deTStack();

    deBoolean   Push(const T& ItemData);
    deBoolean   Push(const T& ItemData, T* &ref);
    deBoolean   Pop();
    deBoolean   Pop(T & target);
    T*          Peek(int ItemOffset);
    T*          Peek();
    deBoolean   Clear();
    deBoolean   isEmpty()   { return (ItemCount == 0); }
    int Length(void)    { return ItemCount; }
    deStackType GetStackType(void) { return StackType; }
    void SetStackType(deStackType PopOrder) { StackType = PopOrder; }
    bool HasData(T & data);

    class TStackNode
    {
    public:
        TStackNode(const T & ref) : Data(ref) {}

        TStackNode * Next;
        TStackNode * Prev;
        T Data;
    };

private:
    TStackNode  *Head;
    TStackNode  *Tail;
    int         ItemCount;
    deStackType StackType;

    TStackNode *InsertItem(TStackNode *PrevItem, TStackNode *NextItem, const T& ItemData);
    TStackNode *AppendItem(const T& ItemData);
    deBoolean RemoveItem(TStackNode *sn);
    T* GetFirstItem(TStackNode *&sn);
    T* GetLastItem(TStackNode *&sn);
    T* GetNextItem(TStackNode *&sn);
    T* GetPrevItem(TStackNode *&sn);
};


/*********************************************************************/
// templated implementation below
/*********************************************************************/


template <class T>
deTStack<T>::deTStack()
{
   ItemCount = 0;
   Head      = NULL;
   Tail      = NULL;
   StackType = LIFO_STACK;
}

template <class T>
deTStack<T>::deTStack(deStackType PopOrder)
:StackType(PopOrder)
{
   ItemCount = 0;
   Head      = NULL;
   Tail      = NULL;
}

template <class T>
deTStack<T>::deTStack(const deTStack<T> &Stack)
{
   TStackNode *sn;

   ItemCount    = 0;
   Head         = NULL;
   Tail         = NULL;
   StackType    = Stack.StackType;

   if (Stack.Head == NULL)
      return;

   sn = Stack.Head;

   while (sn != NULL)
   {
      AppendItem(sn->Data);
      sn = sn->Next;
   }
}

template <class T>
deTStack<T>::~deTStack()
{
    Clear();
}


template <class T>
deBoolean deTStack<T>::Push(const T& ItemData)
{
    TStackNode *sn;

    sn = AppendItem(ItemData);

    if (sn == NULL)
        return (DE_FALSE);

    return (DE_TRUE);
}

template <class T>
deBoolean deTStack<T>::Push(const T& ItemData, T* &ref)
{
    TStackNode *sn;
    
    sn = AppendItem(ItemData);
    
    if (sn == NULL)
        return (DE_FALSE);

    ref = &(sn->Data);
    return (DE_TRUE);
}

template <class T>
deBoolean deTStack<T>::Pop()
{
    TStackNode *sn = NULL;

    if (ItemCount == 0)
        return DE_FALSE;

    if (StackType == LIFO_STACK)
        GetLastItem(sn);
    else
        GetFirstItem(sn);

    if (!RemoveItem(sn))
    {
        //Need error handling here
    }

    return DE_TRUE;
}

template <class T>
deBoolean deTStack<T>::Pop(T & target)
{
    TStackNode *sn = NULL;
    T *pData = NULL;

    if (ItemCount == 0)
        return DE_FALSE;

    if (StackType == LIFO_STACK)
        pData = GetLastItem(sn);
    else
        pData = GetFirstItem(sn);

    target = *pData;

    if (!RemoveItem(sn))
    {
        //Need error handling here
    }

    return DE_TRUE;
}

template <class T>
T* deTStack<T>::Peek(int ItemOffset)
{
    if (ItemCount == 0)
      return NULL;

    if ((ItemCount < (ItemOffset + 1)) || (ItemOffset < 0))
        return NULL;
    
    TStackNode *sn = NULL;
    T* pData = NULL;
    int i;
    
    if (StackType == LIFO_STACK)
    {
        pData = GetLastItem(sn);

        for (i = ItemOffset; i > 0; i--)
        {
            pData = GetPrevItem(sn);
        }
    }
    else
    {
        pData = GetFirstItem(sn);

        for (i = ItemOffset; i > 0; i--)
        {
            pData = GetNextItem(sn);
        }
    }

    return pData;
}

template <class T>
T* deTStack<T>::Peek()
{
    if (ItemCount == 0)
        return NULL;
    
    TStackNode * sn = NULL;
    if (StackType == LIFO_STACK)
    {
        return GetLastItem(sn);
    }
    else
    {
        return GetFirstItem(sn);
    }
}

template <class T>
deBoolean deTStack<T>::Clear()
{
   TStackNode *sn;
   TStackNode *Nextsn;

   sn = Head;

   while (sn != NULL)
   {
      Nextsn = sn->Next;
      delete sn;
      --ItemCount;
      sn = Nextsn;
    }

   Head = NULL;
   Tail = NULL;

   if (ItemCount != 0)
   {
       //assert(NULL == "Failed to remove number of nodes matching internal counter in deTStack");
       return DE_FALSE;
   }
   return DE_TRUE;
}

template <class T>
typename deTStack<T>::TStackNode * deTStack<T>::InsertItem(TStackNode *PrevItem, TStackNode *NextItem, const T& ItemData)
{
   TStackNode *NewNode;

   NewNode = new TStackNode(ItemData);

   if (NewNode == NULL)
   {
      //Need error handling here
      return NULL;
   }

   NewNode->Data = ItemData;
   NewNode->Prev = PrevItem;
   NewNode->Next = NextItem;

   // Append
   if (NextItem == NULL)
      Tail = NewNode;

   // Prepend
   if (PrevItem == NULL)
      Head = NewNode;

   //Set Prev/Next pointers
   if (PrevItem != NULL)
      PrevItem->Next = NewNode;

   if (NextItem != NULL)
      NextItem->Prev = NewNode;

   // Increment node count
   ++ItemCount;

   return NewNode;
}

template <class T>
typename deTStack<T>::TStackNode * deTStack<T>::AppendItem(const T& ItemData)
{
   return InsertItem(Tail, NULL, ItemData);
}

template <class T>
deBoolean deTStack<T>::RemoveItem(TStackNode *sn)
{
    // Unlink the node
    if (Head == sn)
    {
        if (sn->Prev == NULL)
        {
            Head = sn->Next;
            if (Head != NULL)
                Head->Prev = NULL;
        }
        else
        {
            //Need error handling here
            return DE_FALSE;
        }
    }
    if (Tail == sn)
    {
    if (sn->Next == NULL)
    {
        Tail = sn->Prev;
        if (Tail != NULL)
            Tail->Next = NULL;
    }
    else
    {
        //Need error handling here
        return DE_FALSE;
    }
    }
    else
    {
        if (sn->Prev != NULL)
        {
            sn->Prev->Next = sn->Next;
        }
        else
        {
            //Need error handling here
            return DE_FALSE;
        }

        if (sn->Next != NULL)
        {
            sn->Next->Prev = sn->Prev;
        }
        else
        {
            //Need error handling here
            return DE_FALSE;
        }
    }

    // Deallocate the node
    delete sn;

    --ItemCount;

    return DE_TRUE;
}

template <class T>
bool deTStack<T>::HasData(T & data)
{
    TStackNode * n = Head;
    while (n)
    {
        if (n->Data == data)
            return true;
        n = n->Next;
    }
    return false;
}

template <class T>
T* deTStack<T>::GetFirstItem(TStackNode *&sn)
{
    if (Head == NULL)
    {
        sn = NULL;
        return NULL;
    }

    sn = Head;

    return &(sn->Data);
}

template <class T>
T* deTStack<T>::GetLastItem(TStackNode *&sn)
{
    if (Tail == NULL)
    {
        sn = NULL;
        return NULL;
    }

    sn = Tail;

    return &(sn->Data);
}

template <class T>
T* deTStack<T>::GetNextItem(TStackNode *&sn)
{
    if (sn == NULL)
        return NULL;

    if (sn->Next == NULL)
    {
        sn = NULL;
        return NULL;
    }

    sn = sn->Next;

    return &(sn->Data);
}

template <class T>
T* deTStack<T>::GetPrevItem(TStackNode *&sn)
{
    if (sn == NULL)
        return NULL;

    if (sn->Prev == NULL)
    {
        sn = NULL;
        return NULL;
    }

    sn = sn->Prev;

    return &(sn->Data);
}

//#pragma warning (default : 4710)

#endif  // End DESTACK_HPP

---